HW#2 --- last modified February 10 2019 21:57:12..

Solution set.

Due date: Sep 28

Files to be submitted:
  Hw2.zip

Purpose:To learn about which kinds of problems can be classified as `P` versus can be classified as `NP`. To show some problems are `NP`-complete.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO2 -- Give a minimal classification of the complexity of a computational problem as being in one of the class L, NL, P, P/poly, NP, coNP, some level of the polynomial hierarchy, PSPACE, E, EXPTIME, decidable, undecidable.

LO3 -- Show the completeness of a complete problem for each of these classes.

Specification:

Do the following problems out of A & B: 1.14, 2.2, 2.16, 2.22, 2.32.

On the day your homework is due I will ask each group to present one problem to me in class.

If you scored above 8 on Hw1 and you work for Hw2 with someone who scored below 8 on Hw1, I will give you a 1pt bonus. Similarly, if you scored below 8 on Hw1 and you work for Hw2 with someone who scored above 8 on Hw1, I will give you a 1pt bonus. Be advised though that all group members must be prepared to answer any question on class presentation day.

Point Breakdown